/* 
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

输入：s = "()[]{}"
输出：true

输入：s = "{[]}"
输出：true

输入：s = "([)]"
输出：false


思路：利用栈结构，如果栈顶是左括号，那么下一个压入的要么是左括号，要么是与栈顶左括号对应的右括号
如果下一个压入的是左括号，直接存入栈
如果下一个压入的是右括号，就判断此时栈顶的左括号是否与压入的右括号对应
*/

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    const n = s.length;
    // 如果长度为奇数直接false
    if (n % 2 === 1) {
        return false;
    }
    // 用哈希结构建立左右括号的对应关系
    const pairs = new Map([
        [')', '('],
        [']', '['],
        ['}', '{']
    ]);
    // 声明栈
    const stk = [];
    for (let ch of s) {
        // 右括号
        if (pairs.has(ch)) {
            // 此时是空栈 或者 栈顶与此右括号对应的左括号不等时返回false
            if (!stk.length || stk[stk.length - 1] !== pairs.get(ch)) {
                return false;
            }
            // 从栈里取出
            stk.pop();
        }
        else {
            // 左括号--存入栈
            stk.push(ch);
        }
    };
    return !stk.length;
};

let strs = "()[]{}"
let res = isValid(strs)
console.log(res);